package Problem;

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;

import maze.Maze;
import maze.MazeGUI;
import maze.Tile;

import Solver.Node;

public class MouseProblem extends Problem {
	
	
	private static int mazeID = 0; // Giving Each Maze a unique ID
	private static String queuingFunc = "";
	
	/**
	 * Defining the mouse problem operators which are up,down,right and left
	 */
	private static ArrayList<String> operators = new ArrayList<String>();
	static {
		operators.add("UP");
		operators.add("Down");
		operators.add("Right");
		operators.add("Left");
	}
	private Node initialState;	
	private static ArrayList<Object> stateSpace = new ArrayList<Object>();

	
	public MouseProblem(Node initialState) {
		super(operators, initialState, stateSpace);
		this.initialState = initialState;

	}

	/**
	 * @param o (Object) given Node representing a maze state
	 * Overriding the goalTest abstract method in the problem 
	 * it simply checks if the mouse has reached the goal or not
	 */
	@Override
	public boolean goalTest(Object o) {

		Node n = (Node) o;
		Maze m = n.getMaze();
		LinkedList<Tile> l = m.getList();
		for (int i = 0; i < l.size(); i++) {
			if (l.get(i).isMouse()
					&& l.get(i).getEnd().getY() == m.getGoal().getY())
				return true;
		}
		return false;
	}


	/**
	 * @param o (Object) given Node representing a maze state
	 * Overriding the path cost abstract method in the problem 
	 * This method returns the path cost from the root node to the given node
	 */
	@Override
	public int pathCost(Object o) {
		Node n = (Node) o;
		if(n.getParent()==null)
			return 0;
		else return n.getParent().getPathCost()+1;
		
	}
	

	/**
	 * @param l  list of Nodes each  represents a maze state
	 * @param n (Node) the node to be inserted
	 * @param d Depth in case of the iterative deepening 
	 * General insert method, which inserts according to the search algorithm
	 */
	private static void insert(LinkedList<Node> l, Node n, int d) {
		if (queuingFunc.equals("BFS")) {
			l.addLast(n);
		} else if (queuingFunc.equals("ID") && d <= n.getDepth()) {
			l.addFirst(n);
		} else if (!queuingFunc.equals("ID")) {
			l.addFirst(n);
		}
	}

	/**
	 * @param l  list of Nodes each  represents a maze state
	 * General remove method, which removes according to the search algorithm
	 */
	private static Node remove(LinkedList<Node> l) {
		if (queuingFunc.equals("BFS") || queuingFunc.equals("ID") || queuingFunc.equals("DFS")) {
			return l.removeFirst();
		} else {
			int min = Integer.MAX_VALUE;
			int minIndex = -1;
			for (int j = 0; j < l.size(); j++) {
				int h = l.get(j).getHeuristicValue();
				if (h < min) {
					min = h;
					minIndex = j;
				}
			}
			return l.remove(minIndex);
		}		
	}

	/**
	 * @param queingFunction ; String represents the searching algorithm which intern indicates
	 * the queuing function
	 * A general implementation of the algorithms, basically in each iteration a node is dequeued
	 * and we generate from it every possible move(state) and enqueue it, removing and inserting 
	 * the node in the queue vary according to the queuing function
	 */
	
	public boolean generalSearch(String queingFunction) throws CloneNotSupportedException {				
		queuingFunc = queingFunction;
		int iterativeCount = 1;
		if (queingFunction.equals("ID")) {
			iterativeCount = Integer.MAX_VALUE;
		}
		int k = 0;		
		while (k < iterativeCount) {
			mazeID = 0;
			Node initial = (Node) initialState;
			LinkedList<Node> q = new LinkedList<Node>();
			LinkedList<Maze> v = new LinkedList<Maze>();
			q.addLast(initial);
			v.addLast(initial.getMaze());			
			while (!q.isEmpty()) {
				Node n = remove(q);
				if (goalTest(n)) {
					getPathToGoal(n);
					return true;
				}
				Maze m = n.getMaze();
				
				for (int i = 0; i < m.getList().size(); i++) {
					Tile t = m.getList().get(i);
					if (t.getOrientation().equals("H")) {
						if (m.canMove(t.getID(), "Left")) {
							Maze r = m.copy();
							r.move(t.getID(), "Left");
							boolean visited = isVisted(v, r);
							if (!visited) {
								r.setId(mazeID++);
								Maze tmp = r.copy();
								Node n2 = new Node(r.getId(), tmp, n, "Tile "
										+ t.getID() + " Left",
										n.getDepth() + 1, n.getPathCost() + 1);
								heuristic(n2);
								insert(q, n2, k);
								v.addLast(n2.getMaze());
							}
						}						
						if (m.canMove(t.getID(), "Right")) {
							Maze r = m.copy();
							r.move(t.getID(), "Right");
							boolean visited = isVisted(v, r);
							if (!visited) {
								r.setId(mazeID++);
								Maze tmp = r.copy();
								Node n2 = new Node(r.getId(), tmp, n, "Tile "+ t.getID() + " Right",
										n.getDepth() + 1, n.getPathCost() + 1);
								heuristic(n2);
								insert(q, n2, k);
								v.addLast(n2.getMaze());
							}
						}
					} else if (t.getOrientation().equals("V")) {
						// move up or down
						if (m.canMove(t.getID(), "Up")) {
							Maze r = m.copy();
							r.move(t.getID(), "Up");
							boolean visited = isVisted(v, r);
							if (!visited) {
								r.setId(mazeID++);
								Maze tmp = r.copy();
								Node n2 = new Node(r.getId(), tmp, n, "Tile "+ t.getID() + " UP", n.getDepth() + 1,
										n.getPathCost() + 1);
								heuristic(n2);
								insert(q, n2, k);
								v.addLast(n2.getMaze());
							}
						}
						if (m.canMove(t.getID(), "Down")) {
							Maze r = m.copy();
							r.move(t.getID(), "Down");
							boolean visited = isVisted(v, r);
							if (!visited) {								
								r.setId(mazeID++);
								Maze tmp = r.copy();
								Node n2 = new Node(r.getId(), tmp, n, "Tile "+ t.getID() + " Down",
										n.getDepth() + 1, n.getPathCost() + 1);
								heuristic(n2);
								insert(q, n2, k);
								v.addLast(n2.getMaze());
							}
						}
					}
				}
			}			
			k++;
		}
		return false;
	}

	/**
	 * @param n ; Node (state of maze)
	 * The function sets the heuristic value for a given node accoring
	 * to the given heurisitic
	 */
	
	private static void heuristic(Node n) {
		if (queuingFunc.equals("GR1")) {
			int h = Heuristics.greedyHeuristic1(n);
			n.setHeuristicValue(h);
		} else if (queuingFunc.equals("GR2")) {
			int h = Heuristics.greedyHeuristic2(n);
			n.setHeuristicValue(h);
		} else if (queuingFunc.equals("AS1")) {
			int h = Heuristics.aStarHeuristic1(n);
			n.setHeuristicValue(h);
		} else if (queuingFunc.equals("AS2")) {
			int h = Heuristics.aStarHeuristic2(n);
			n.setHeuristicValue(h);
		}	
	}

	/**
	 * @param n ; Node (state of maze : Goal Node)
	 * The method prints the path to goal and then call the GUI
	 */
	
	private void getPathToGoal(Node n) {
		System.out.println("Search using: " + queuingFunc);
		System.out.println("Path Cost: " + n.getPathCost());
		int pc = n.getPathCost();
		LinkedList<Node> nodes = new LinkedList<Node>();
		while (n != null) {
			nodes.addFirst(n);			
			Maze m = n.getMaze();
			System.out.println(n.getOperator());
			m.display();
			n = n.getParent();
		}
		new MazeGUI(nodes, queuingFunc, pc);
	}

	/**
	 * @param v ; List of visited mazes
	 * @param n ; Node (state of maze)
	 * checks whether a node has been visited or not
	 * 	 */
	
	private static boolean isVisted(LinkedList<Maze> v, Maze r) {
		for (int i = 0; i < v.size(); i++) {
			if (v.get(i).equals(r))
				return true;
		}
		return false;
	}

	public static void main(String[] args) throws CloneNotSupportedException, IOException {		
		Maze m = new Maze();
		m.display();
		Node n = new Node(0, m, null, "", 0, 0);
		MouseProblem mp = new MouseProblem(n);
		
		//System.out.println(mp.generalSearch("ID"));
		//System.out.println(mp.generalSearch("BFS"));
		//System.out.println(mp.generalSearch("DFS"));
		//System.out.println(mp.generalSearch("GR1"));
		//System.out.println(mp.generalSearch("GR2"));
		System.out.println(mp.generalSearch("AS1"));
		//System.out.println(mp.generalSearch("AS2"));
	}
}
